1) Простая моделька.
Переменная берем ли мы элемент i в подмножество . Всего одно условие: каждый элемент содержится в одном подмножестве, притом только в одном, то есть Соответсвенно, целевая функция будет иметь вид: К сожалению, она не линейная.
StasFomin: Ну тут как раз надо было подумать, как сделать ее линейной. У нас было много подобного даже в бизнес-задачах.
Визуализация.
По оси абсцисс отмечены индексы элементов () и в скобках их веса (). По оси ординат — множество, в которое берем
2. Модель посложнее (она теперь линейная)
Идея: сначала раскроем квадрат Пусть теперь . Тогда целевая функция будет иметь вид:
Построение модели:
"Диагональные" элементы обозначают берем ли мы элемент в подмножество .
Если () и (), то . И обратно.
Отсюда:
(так модель вынуждена ставить ноль в , если ).
(так модель вынуждена ставить 1 в , если и ).
3. Модель прошлого пункта можно упростить:
a) Заметим, что модели "не выгодно" ставить в единицу, если она может поставить туда ноль (так как целевая функция на минимум). Благодаря этому можно выбросить условие empty_rows
(), так как и без него модель предпочтет ставить 0 в .
b) Также можно заполнять не все , а только половину (из симметричной матрицы перейдем в верхнетреугольную). Tогда нужно скорректировать целевую функцию: квадраты () в сумме должны умножаться на 1, а "перекрестные" элементы () на 2.
Как мы можем видеть, число условий Constraint уменьшилось почти в 4 раза.